/*************************************************************************
	> File Name: OptBST.cpp
	> Author: 
	> Mail: 
	> Created Time: 日 12/27 14:28:29 2015
 ************************************************************************/

#include<iostream>
#include<cstring>

using namespace std;

void OPTBST(double ** &e, double ** &w, int ** &root, double *arr, double *brr, int len) {
    e = new double* [len + 2];
    w = new double* [len + 2];
    root = new int* [len + 2];
    for (int i = 0; i < len + 2; ++i) {
        e[i] = new double [len + 1];
        w[i] = new double [len + 1];
        root[i] = new int [len + 1];
    }
    for (int i = 1; i < len + 2; ++i) {
        e[i][i - 1] = arr[i - 1];
        w[i][i - 1] = arr[i - 1];
        
    }
    for (int i = 0; i < len - 2; ++i) {
        memset(root[i], 0, sizeof(int) * (len + 1));
    }
    for (int l = 1; l <= len; ++l) {
        for (int i = 1; i <= len - l + 1; ++i) {
            int j = i + l - 1;
            w[i][j] = w[i][j - 1] + arr[j] + brr[j];
            e[i][j] = e[i][j - 1] + e[j + 1][j] + w[i][j];
            root[i][j] = j;
            for (int r = i; r < j; ++r) {
                if (e[i][j] > e[i][r - 1] + e[r + 1][j] + w[i][j]) {
                    e[i][j] = e[i][r - 1] + e[r + 1][j] + w[i][j];
                    root[i][j] = r;
                }
            }
        }
    }
}
void outresult(int **root, int i, int j) {
    if (i > j)
        return;
    int r = root[i][j];
    cout << "root is:" << r << endl;
    cout << "left tree ..." << endl;
    outresult(root, i, r - 1);
    cout << "right tree ..." << endl;
    outresult(root, r + 1, j);
}
int main(void) {
    double arr[6] = {0.1, 0.01, 0.02, 0.04, 0.03, 0.2};
    double brr[6] = {0, 0.15, 0.05, 0.075, 0.25, 0.075};      //the first element is not used
    double **e, **w;
    int **root;
    OPTBST(e, w, root, arr, brr, 5);
    outresult(root, 1, 5);
    cout << "the minimal value is " << e[1][5] << endl;
    return 0;
}
